#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstdint>
#include <ctime>
#include <stack>
#include <string>

using namespace std;

//对每一行利用最大面积计算公式
//需要先计算每一行，在不同列处的高度
class Solution {
public:
    vector<vector<vector<char>>> test;
    int maxArea(vector<int> height) 
    {
        stack<int> sta;
        int maxArea = 0;
        int i;
        sta.push(-1);
        for (i = 0; i < height.size(); i++){
            if (sta.top() == -1){
                sta.push(i);
            }else{
                if (height[sta.top()] < height[i]){
                    sta.push(i);
                }else{
                    while(sta.top() != -1){
                        int hi = height[sta.top()];
                        if (height[i] > hi){
                            break;
                        }
                        sta.pop();
                        int area = (i - sta.top() -1) * hi;
                        maxArea = max(maxArea, area);
                    }
                    sta.push(i);
                }
            }
        }
        while(sta.top() != -1){
            int hi = height[sta.top()];
            sta.pop();
            int area = (i - sta.top() -1) * hi;
            maxArea = max(maxArea, area);
        }
        return maxArea;
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.size() == 0) return 0;
        vector<int> length(matrix[0].size(), 0);
        int maxRec = 0;
        // cout << "matrix.size() is " << matrix.size() << endl;
        for (int i = 0; i < matrix.size(); i++){
            // cout << "matrix line " << i << endl;
            for (int j = 0; j < matrix[0].size(); j++){
                if (matrix[i][j] == '1'){
                    length[j]++;
                }else{
                    length[j] = 0;
                }
                // cout << length[j] << " " ;
            }
            // cout << endl;
            int area = maxArea(length);
            // cout << "max erea is: " << area << endl;
            maxRec = max(maxRec, area);
        }
        return maxRec;
    }
};

int main()
{
    Solution su;

     su.test.push_back(vector<vector<char>>(
         {
             {'1','0','1','0','0'},
             {'1','0','1','1','1'},
             {'1','1','1','1','1'},
             {'1','0','0','1','0'}
         }
         ));

     for (int i = 0; i < su.test.size(); i++){
         int result = su.maximalRectangle(su.test[i]);
         cout << "result is " << result << endl;
     }
    return 0;
}
